package com.fw.leetcode.matrix;

import com.fw.leetcode.LeetCode;

import java.util.Arrays;

/**
 * 48. Rotate Image
 *
 * You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
 *
 * You have to rotate the image in-place, which means you have to modify the input 2D matrix directly.
 * DO NOT allocate another 2D matrix and do the rotation.
 *
 * Example 1:
 *  Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
 *  Output: [[7,4,1],[8,5,2],[9,6,3]]
 *
 * Example 2:
 *  Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
 *  Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
 *
 * Constraints:
 *  n == matrix.length == matrix[i].length
 *  1 <= n <= 20
 *  -1000 <= matrix[i][j] <= 1000
 */
public class Num_0048 implements LeetCode {

    private interface Solution {
        void rotate(int[][] matrix);

        default void assertExpected(int[][] matrix, int[][] expected) {
            int[][] oldMatrix = new int[matrix.length][matrix[0].length];
            for (int i = 0; i < oldMatrix.length; i++) {
                System.arraycopy(matrix[i], 0, oldMatrix[i], 0, oldMatrix[i].length);
            }
            rotate(matrix);
            for (int i = 0; i < matrix.length; i++) {
                if (!Arrays.equals(matrix[i], expected[i])) {
                    rotate(oldMatrix);
                }
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public void rotate(int[][] matrix) { // 矩阵顺时针旋转90度：时O(n^2) 空O(1)
            /*
             *  [ 1, 2, 3, 4]      [14,10, 5, 1]
             *  [ 5, 6, 8, 9]  ->  [15,11, 6, 2]
             *  [10,11,12,13]      [16,12, 8, 3]
             *  [14,15,16,17]      [17,13, 9, 4]
             *
             * 公式 matrix[row][col] -> matrix[col][n-1-row] 不区分层
             * 层只用于按层遍历
             */
            int layer = 0;
            int n = matrix.length;
            while (layer <= matrix.length / 2) {
                int i = layer;
                for (int j = i; j < n - 1 - layer; j++) {
                    /*
                     * 四角公式
                     * matrix[i][j]      →      matrix[j][n-1-i]
                     *     ↑                       ↓
                     * matrix[n-1-j][i]  ←      matrix[n-1-i][n-1-j]
                     */
                    int tmp = matrix[i][j];
                    matrix[i][j] = matrix[n-1-j][i];
                    matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                    matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                    matrix[j][n-1-i] = tmp;
                }
                layer++;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertExpected(new int[][]{{1,2,3},{4,5,6},{7,8,9}}, new int[][]{{7,4,1},{8,5,2},{9,6,3}});
        solution.assertExpected(new int[][]{{5,1,9,11},{2,4,8,10},{13,3,6,7},{15,14,12,16}}, new int[][]{{15,13,2,5},{14,3,4,1},{12,6,8,9},{16,7,10,11}});
    }
}
